package DoExercise.左程云基础班;

public class Code_02_链表结构栈队列递归行为哈希表和有序表
{
    public static class Node
    {
        public int value;
        public Node next;

        public Node(int data)
        {
            value = data;
        }
    }

    public static class DoubleNode
    {
        public int value;
        public DoubleNode last;
        public DoubleNode next;

        public DoubleNode(int data)
        {
            value = data;
        }
    }

    /**
     * 单链表逆转
     *
     * @param head
     * @return
     */
    public static Node reverseNode(Node head)
    {
        Node pre = null;
        Node next = null;

        while (head.next != null)
        {
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return head;
    }

    /**
     * 双向链表逆转
     *
     * @param head
     * @return
     */
    public static DoubleNode reverseDoubleList(DoubleNode head)
    {
        DoubleNode pre = null;
        DoubleNode next = null;

        while (head.next != null)
        {
            next = head.next;
            head.next = pre;
            head.last = next;
            pre = head;
            head = next;
        }
        return head;
    }

    /**
     * 删除head中的value
     *
     * @param head
     * @param value
     * @return
     */
    public static Node deleteNodeVal(Node head, int value)
    {
        while (head != null)
        {
            if (head.value != value) break;
            head = head.next;
        }

        Node pre = head;
        Node cur = head;

        while (cur != null)
        {
            if (cur.value == value)
            {
                pre.next = cur.next;
            } else
            {
                pre = cur;
            }
            cur = cur.next;
        }
        return head;
    }


    public static void main(String[] args)
    {
        Node head = new Node(1);
        Node node1 = new Node(2);
        Node node2 = new Node(3);
        Node node3 = new Node(4);
        head.next = node1;
        node1.next = node2;
        node2.next = node3;

        while (head != null)
        {
            System.out.print(head.value+" ");
            head = head.next;
        }

        reverseNode(head);

        while (head != null)
        {
            System.out.print(head.value+" ");
            head = head.next;
        }
    }


}
